package com.ryujung.linked_list.leetCode_160;

/*
Write a program to find the node at which the intersection of two singly linked 
lists begins.

Example:
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 
(note that this must not be 0 if the two lists intersect). 
From the head of A, it reads as [0,9,1,2,4]. From the head of B, 
it reads as [3,2,4]. There are 3 nodes before the intersected node in A; 
There are 1 node before the intersected node in B.


- If the two linked lists have no intersection at all, return null.
- The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
*/
//Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

/**
 * 160 判断两个链表相交,被找到该节点
 * 
 * 思路: 方法一: 首先容易想到的是使用HashSet<ListNode>依次放入两个链表,在放第二个链表时进行判断,
 * 如果已经存在,就是目标节点.如果没有重复,返回null 
 * 时间复杂度O(n+m) 
 * 空间复杂度O(n+m) 可以优化, 思考其他方法
 * 
 * 方法二:双指针 非常巧妙的方法,让两个指针分别去遍历两个链表, 
 * 当遍历A的指针到达尾部,让指针指向B链表的头部,继续遍历
 * 同样,当遍历B的指针到达尾部,让指针指向A链表的头部,继续遍历
 * 
 * 当两个指针都将A+B都遍历一遍后,两个指针将同步,如果有交集,就会在后面的遍历中同时渠道相同的值
 * 如果两个指针的节点相同,则返回相同的节点即可,如果不相同,则指针遍历到null,返回null
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null)
            return null;

        // 定义双指针
        ListNode tempA = headA;
        ListNode tempB = headB;

        //
        while (tempA != tempB) {//跳出循环的条件是指向相同的节点或者同指向null
            tempA = tempA == null ? headB : tempA.next;
            tempB = tempB == null ? headA : tempB.next;
        }

        return tempA;
    }
}